package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-05 23:40
 **/
public class LeetCode148 {

    public ListNode sortList(ListNode head) {
        return split(head);
    }

    ListNode split(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode tou = new ListNode();
        tou.next = head;
        ListNode fast = head;
        ListNode slow = tou;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //分隔的第二个链表的头结点
        ListNode head2 = slow.next;
        slow.next = null;

        ListNode newHead = split(head);
        ListNode newHead2 = split(head2);
        return merge(newHead, newHead2);
    }

    ListNode merge(ListNode head, ListNode head2) {
        ListNode tou = new ListNode();
        ListNode slow = tou;
        while (head != null && head2 != null) {
            if (head.val <= head2.val) {
                slow.next = head;
                slow = slow.next;
                head = head.next;
            } else {
                slow.next = head2;
                slow = slow.next;
                head2 = head2.next;
            }
        }

        while (head != null) {
            slow.next = head;
            slow = slow.next;
            head = head.next;
        }

        while (head2 != null) {
            slow.next = head2;
            slow = slow.next;
            head2 = head2.next;
        }
        return tou.next;
    }
}
